#include "AlgorithmsTests.h"
#include "GreedyFIllGroupAlgorithm.h"
#include "GreedyFillMaximalGroupAlgorithm.h"
#include "BreakAndRefillGroupAlgorithm.h"
#include "SwitchVerticesAlgorithm.h"
#include "stdafx.h"
#include "TestUtils.h"
#include "VertexDirectory.h"
#include <cstdlib>
#include <iostream>

using namespace std;

// updates the original chain according to the copy chain, and frees the 
// Unnecessary resources
void UpdateOriginalChainFromCopy(Chain& originalChain, Chain& copyChain)
{
	// we save pointers to the chain groups, so we can free them after the copy.
	list<Group*> groupsToDelete = originalChain.ChainGroups();
	Chain* tempChainPointer = copyChain.CloneFromVertexDirectoryAndUpdateIt(NULL);
	if (tempChainPointer == NULL)	//memory allocation failed
	{
		Debug::PrintDebugMsg("ERROR: unable to update the chain in UpdateOriginalChainFromCopy.");
	}
	originalChain = *(tempChainPointer);
	
	originalChain = *(copyChain.CloneFromVertexDirectoryAndUpdateIt(NULL));
	list<Group*>::iterator groupIt;
	for (groupIt = groupsToDelete.begin(); groupIt != groupsToDelete.end(); groupIt++)
	{
		delete (*groupIt);
	}
}

// try to improve the given group, using the algorithm specified in
// algorithm variable.
// algorithm == 1 means FillSingles
// algorithm == 2 means FillCouples
// algorithm == 3 means FillMaximalGroup
// algorithm == 4 means Break&RefillGroup
TestUtils::TestResult RunAlgorithm(Graph& graph, Group& group, int algorithm, InputVariables* inputVariables, VertexDirectory* dir)
{
	if ((algorithm < 1) || (algorithm > 4))
	{
		Debug::PrintDebugMsg("unrecognized algorithm number passed to ImproveChainBySingleFillingOfGroups: " + algorithm);
		return TestUtils::TestFailed;
	}
	switch (algorithm)
	{
	case 1: GreedyFillGroupAlgorithm::FillSingles(graph, group, dir, Algorithms::_NO_SIZE_LIMITATION);
			break;
	case 2: GreedyFillGroupAlgorithm::FillCouples(graph, group, dir, Algorithms::_NO_SIZE_LIMITATION);
			break;
	// switch the last to false later!!
	case 3: GreedyFillMaximalGroupAlgorithm::Fill(graph, group, inputVariables->numberOfIterationsForGreedySearch,
				inputVariables->percentOfVerticesToStartImprovedGreedy, inputVariables->percentOfVerticesToStopImprovedGreedy,
				inputVariables->numberOfPairsInImprovedGreedy, dir, true);
			break;
	case 4: BreakAndRefillGroupAlgorithm::BreakAndRefill(graph, group, inputVariables->numberOfIterationsForGreedySearch,
				inputVariables->breakingPercentage, inputVariables->percentOfVerticesToStartImprovedGreedy,
				inputVariables->percentOfVerticesToStopImprovedGreedy, inputVariables->numberOfPairsInImprovedGreedy, dir);
			break;
	}
	return TestUtils::TestPassed;
}


// try to improve the given group using an algorithms according to algorithm paramter:
TestUtils::TestResult ImproveSingleGroup(Group& group, Chain& chain, int algorithm, VertexDirectory* dir, InputVariables* inputVariables)
{
		// try to fill the group, using the greedy fill algorithm for singles
		int groupSize = group.Size();
		Graph* graph = chain.GetGraph();
		list<Group*> groups = chain.ChainGroups();
		set<int> groupNames = chain.ChainGroupNames();
	
		
		// run the apropriate algorithm 
		if (RunAlgorithm(*graph, group, algorithm, inputVariables, dir) == TestUtils::TestFailed)
		{
			return TestUtils::TestFailed;
		}
		
		// validate the results:
		// validate the graph & group state after the filling algorithm: make sure they 
		// were updated correctly from the copies
		if (Algorithms::ValidateVertexDirectoryState(graph, groups, groupNames, dir) == false)
		{
			return TestUtils::TestFailed;
		}
		// validate the new group isn't smaller than the original one
		if (TestUtils::VerifyIsTrue(group.Size() >= groupSize,"The new group is smaller than the original one") == TestUtils::TestFailed)
		{
			return TestUtils::TestFailed;
		}
		// validate the new group is independent
		if (TestUtils::VerifyIsTrue(Algorithms::ValidateGroupIsIndependent(&group),"The new group isn't independent") == TestUtils::TestFailed)
		{
			return TestUtils::TestFailed;
		}
		// validate the groups in the chain are disjoint in pairs 
		if (TestUtils::VerifyIsTrue(Algorithms::ValidateGroupInChainIsDisjoint(&chain, &group),"The new chain contains groups that aren't disjoint") == TestUtils::TestFailed)
		{
			return TestUtils::TestFailed;
		}
		return TestUtils::TestPassed;
}

// Runs the specified algorithm to create a new group to add to chain and returns a new chain with an extra group
// algorithm == 1 means FillSingles
// algorithm == 2 means FillCouples
// algorithm == 3 means FillMaximalGroup
// algorithm == 4 means Break&RefillGroup
Chain *UseAlgorithmToAddToChain(Chain *oldChain, int algorithm, int groupIndex, InputVariables *inputVariables)
{
		// try to fill the group, using the greedy fill algorithm for singles
		Chain *newChain;
		Graph* graph = oldChain->GetGraph();
		list<Group*> groups = oldChain->ChainGroups();
		set<int> groupNames = oldChain->ChainGroupNames();
		VertexDirectory *dir = oldChain->GetDirectory();
		Group* group = new Group(groupIndex, dir);
		string message1 = "The new group isn't independent";
		SwitchVerticesAlgorithm algo = SwitchVerticesAlgorithm(oldChain);

		switch (algorithm)
		{
			case 1:
			case 2:
			case 3:
			case 4:
				
				// run the apropriate algorithm 
				if (RunAlgorithm(*graph, *group, algorithm, inputVariables, dir) == TestUtils::TestFailed)
				{
					return NULL;
				}
				// Verify new group is independent
				if (TestUtils::VerifyIsTrue(Algorithms::ValidateGroupIsIndependent(group),message1) == TestUtils::TestFailed)
				{
					return NULL;
				}
				// Create a new chain to return
				newChain = oldChain->CloneFromVertexDirectoryAndUpdateIt(dir);
				newChain->AddGroup(group);
				return newChain;
				break;
			case 5:
				oldChain->AddGroup(group);
				newChain = algo.SwitchSingles();
				return newChain;
				break;
			case 6:
				oldChain->AddGroup(group);
				newChain = algo.SwitchCouples();
				return newChain;
				break;
				
			
		}
		
		Debug::PrintDebugMsg("Unsupported algorithm number " + algorithm);
		return NULL;
}

// Scenario: get a chain, try to improve each of its groups with the algorithm specified in
// algorithm variable.
// algorithm == 1 means FillSingles
// algorithm == 2 means FillCouples
// algorithm == 3 means FillMaximalGroup
// algorithm == 4 means Break&RefillGroup
// startImprovingIndex: the function won't try to inprove the first improveStartingIndex groups in the chain
// Note: the counting starts at 1 (and not 0). Therefore, if the first 2 groups shouldn't be improved 
// (improvements should start at the 3rd group) then startImprovingInde should equal 3.
// make sure the chain wasn't downgraded as a result of the operations
TestUtils::TestResult ImproveChainBySingleFillingOfGroups(int n, int w, Chain& chain, int algorithm, InputVariables* inputVariables, int startImprovingIndex) 
{
	if (startImprovingIndex > chain.GetLength())
	{
		Debug::PrintDebugMsg("ImproveChainBySingleFillingOfGroups didn't try to improve any group because the improve starting index was bigger than the chain length.");
		return TestUtils::TestPassed;
	}
	// create a copy of the vertex direcotry and the chain
	VertexDirectory* dir = new VertexDirectory(VertexDirectory::GetStaticCopyVertices());
	Chain* newChain = chain.CloneFromVertexDirectoryAndUpdateIt(dir);
	if (newChain == NULL)	//memory allocation failed
	{
		Debug::PrintDebugMsg("chain wasn't created in ImproveChainBySingleFillingOfGroups and the test didn't run.");
		delete dir;
		return TestUtils::TestFailed;
	}
	Graph* graph = newChain->GetGraph();
	map<vector<bool>, Vertex*>* vertices = VertexDirectory::GetStaticCopyVertices();

	list<Group*> groups = newChain->ChainGroups();
	set<int> groupNames = newChain->ChainGroupNames();
	list<Group*>::iterator it = newChain->Begin();
	//increase the iterator until reaching the group index from which we should try to improve the groups
	for (int i=1; i<startImprovingIndex; i++)
	{
		it++;
	}

	for (; it != newChain->End(); it++)
	{
		// try to fill the group
		int originalGroupSize = (*it)->Size();
		if (ImproveSingleGroup(*(*it), *newChain, algorithm, dir, inputVariables) == TestUtils::TestFailed)
		{
			return TestUtils::TestFailed;
		}
		string str = "Group size after improvements: ";
		str	+= (*it)->Size();
		str += ". Original group size: ";
		str += originalGroupSize;
		Debug::PrintDebugMsg(str);
	}

	// copy the improved chain into the original chain
	UpdateOriginalChainFromCopy(chain, *newChain);
	delete newChain;
	// validate all the data was updated correctly in the static copies
	if (Algorithms::ValidateVertexDirectoryState(chain.GetGraph(), chain.ChainGroups(), chain.ChainGroupNames()) == false)
	{
		Debug::PrintDebugMsg("static vertex directory not updated correctly after inproving the chain in ImproveChainBySingleFillingOfGroups");
		return TestUtils::TestFailed;
	}
	
	return TestUtils::TestPassed;
}

// Scenario: get a chain, try to find the next group using one of the greedy algorithms:
// algorithm == 1 means FillSingles
// algorithm == 2 means FillCouples
// algorithm == 3 means FillMaximalGroup
// algorithm == 5 means switch singles
// algorithm == 6 means switch couples
// if improveGroup == true, after filling the group, the test will try to improve it using
// algorithms 3 & 4.
TestUtils::TestResult FindNextGroupInChain(int n, int w, int algorithm, 
						int NumberOfGroupsToFind, Chain& chain, InputVariables* variables, bool improveGroup) 
{
	// create a copy of the vertex direcotry and the chain
	VertexDirectory* dir = new VertexDirectory(VertexDirectory::GetStaticCopyVertices());
	Chain* newChain = chain.CloneFromVertexDirectoryAndUpdateIt(dir);
	if (newChain == NULL)	//memory allocation failed
	{
		Debug::PrintDebugMsg("chain wasn't created in FindNextGroupInChain and the test didn't run.");
		delete dir;
		return TestUtils::TestFailed;
	}
	
	// so we won't create groups with names that are already in use
	int buffer = 1000;
	Graph* graph = newChain->GetGraph();
		
	for (int i=1; i <= NumberOfGroupsToFind; i++)
	{
		newChain = UseAlgorithmToAddToChain(newChain,algorithm,i+buffer,variables);
		string noChainMessage = "Chain is empty, algorithm failed";
		if (TestUtils::VerifyIsTrue(newChain != NULL, noChainMessage) == TestUtils::TestFailed)
		{
			return TestUtils::TestFailed;
		}
		Graph *graph = newChain->GetGraph();
		string noGraphMessage = "graph is empty, algorithm failed";
		if (TestUtils::VerifyIsTrue(graph != NULL, noGraphMessage) == TestUtils::TestFailed)
		{
			return TestUtils::TestFailed;
		}

		Group *group = newChain->GetGroup(newChain->GetMaxGroupIndex());
		string noGroupMessage = "new group with its new Id is not found, algorithm failed";
		if (TestUtils::VerifyIsTrue(group != NULL, noGroupMessage) == TestUtils::TestFailed)
		{
			return TestUtils::TestFailed;
		}
		
		// validate the results
		// validate the graph & group state after the filling algorithm: make sure they 
		// were updated correctly from the copies
		if (Algorithms::ValidateVertexDirectoryState(graph, newChain->ChainGroups(), newChain->ChainGroupNames(), newChain->GetDirectory()) == false)
		{
			return TestUtils::TestFailed;
		}
		// print new group info
		std::stringstream streamStr;
		streamStr <<"Group " << group->GetGroupName() << " found in iteration #" << i << " has size " << group->Size() << ".";
		Debug::PrintDebugMsg(streamStr.str());

		if (improveGroup == true)
		{
			if (ImproveSingleGroup(*group, *newChain, 4, dir, variables) == TestUtils::TestFailed)
			{
			return TestUtils::TestFailed;
			}
			// print new group info
			std::stringstream streamStr;
			streamStr << "After improvment by breaking group greedy search, group " << group->GetGroupName() <<" has size " << group->Size() << ".";
			Debug::PrintDebugMsg(streamStr.str());
		}

		string message2 = "The new chain isn't better then the original chain, due to group #" + i;
		//validate this chain is at least as good as the given chain
		if (TestUtils::VerifyIsTrue(newChain->CompareSubChains(&chain, i) >= 0,message2) == TestUtils::TestFailed)
		{
			return TestUtils::TestFailed;
		}		
		
		Debug::PrintDebugMsg("Chain found: ");
		newChain->Print();
	}
	// copy the improved chain into the original chain
	Chain* tempChainPointer = newChain->CloneFromVertexDirectoryAndUpdateIt(NULL);
	if (tempChainPointer == NULL)	//memory allocation failed
	{
		Debug::PrintDebugMsg("ERROR: unable to update the chain in FindNextGroupInChain, the algorithm didn't run.");
		return TestUtils::TestFailed;
	}
	chain = *(tempChainPointer);
	
	delete newChain;
	// validate all the data was updated correctly in the static copies
	if (Algorithms::ValidateVertexDirectoryState(chain.GetGraph(), chain.ChainGroups(), chain.ChainGroupNames()) == false)
	{
		Debug::PrintDebugMsg("static vertex directory not updated correctly after inproving the chain in FindNextGroupInChain");
		return TestUtils::TestFailed;
	}
	
	return TestUtils::TestPassed;
}
